package com.youth.day01;

/**
 *  快速排序
 *
 *  额外收获：
 *  1. System.arraycopy() ：最后一个参数不是目标数组的结束角标，而是要复制的长度。
 *  2. 多年来，快排的思路都错了。  元素是和<strong>基数</strong>比较  而不是和角标指着的数比较。
 *
 * @author Jinx
 * @date 2021/6/12 21:25
 */
public class FastSort {


    /**
     *  时间复杂度：O(nlog2ⁿ)
     *  理解：
     *  while循环 n 次
     *  假设每次平均，递归次数总是一半一半的减  可近似为log2ⁿ
     */
    public static int[] sort(int[] arr){
        if(arr == null || arr.length <= 1){
            return arr;
        }

        // 头尾指针   基数
        int head = 0, tail = arr.length - 1, base = arr[0];

        // 参照物标记   true:尾指针（以尾指针为主体进行比较移动）   false：头指针
        boolean flag = true;

        while (head < tail){
            if(flag){
                if(arr[tail] > base){
                    tail--;
                }else {
                    arr[head++] = arr[tail];
                    flag = false;
                }
            }else {
                if(arr[head] < base){
                    head++;
                }else {
                    arr[tail--] = arr[head];
                    flag = true;
                }
            }
        }
        arr[head] = base;


        // 遍历完后  数组左右有序   再将左右有序的数组递归
        int[] left = new int[head + 1];
        int[] right = new int[arr.length - left.length];
        System.arraycopy(arr, 0, left, 0, left.length);
        System.arraycopy(arr, left.length, right, 0, right.length);

        // 合并为新数组
        System.arraycopy(sort(left), 0, arr, 0, left.length);
        System.arraycopy(sort(right), 0, arr, left.length, right.length);

        return arr;
    }
}
